package top.datacluster.basic.algorithm.leetcode.queue;

import java.util.LinkedList;

public class LeetCode1604_1 {

    private LinkedList<Integer> queue = new LinkedList<>();

    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] result = new int[nums.length - k + 1];
        for (int i = 0; i < k; i++){
            push(nums[i]);
        }
        for (int i = k; i < nums.length; i++){
            result[i-k] = get(nums[i]);
            push(nums[i]);
        }
        result[result.length - 1] = get(nums[nums.length -1]);
        return result;
    }


    public void push(int n){
        if (queue.isEmpty()){
            queue.offerLast(n);
        }else{
            while (!queue.isEmpty() && queue.peekLast() < n){
                queue.pollLast();
            }
            queue.offerLast(n);
        }
    }

    public int get(int n){
        return n == queue.peekFirst() ? queue.pollFirst() : queue.peekFirst();

    }

    public static void main(String[] args) {
        int[] test = new int[]{1,3,-1,-3,5,3,6,7};
        System.out.println(new LeetCode1604_1().maxSlidingWindow(test, 3));
    }
}
